class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0
        rows = len(matrix)
        cols = len(matrix[0])
        DP = [[0 for _ in range(cols)] for _ in range(rows + 1)]
        max_value = 0
        for i in range(1, rows + 1):
            for j in range(cols):
                if matrix[i - 1][j] == '1':
                    DP[i][j] = DP[i - 1][j] + 1
        for i in range(1, rows + 1):
            DP[i].insert(0, 0)
            DP[i].append(0)
            now_layer = DP[i]
            stack = [0]
            for j in range(1, len(now_layer)):
                if now_layer[j] >= now_layer[stack[-1]]:
                    stack.append(j)
                else:
                    while now_layer[stack[-1]] > now_layer[j]:
                        index = stack.pop()
                        max_value = max(now_layer[index] * (j - stack[-1] - 1), max_value)
                    stack.append(j)
        return max_value


data = Solution()
matrix = [["0","0"]]
print(data.maximalRectangle(matrix))